//给你一个整数数组 nums 和一个 正整数 k 。 
//
// 请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。 
//
// 子数组是数组中的一个连续元素序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,2,3,3], k = 2
//输出：6
//解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 
//。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,4,2,1], k = 3
//输出：0
//解释：没有子数组包含元素 4 至少 3 次。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// 1 <= nums[i] <= 10⁶ 
// 1 <= k <= 10⁵ 
// 
//
// Related Topics 数组 滑动窗口 👍 76 👎 0


package LeetCode.editor.cn;


import java.util.*;

/**
 * @author ldltd
 * @date 2025-04-29 11:38:30
 * @description 2962.统计最大元素出现至少 K 次的子数组
 
 */
 
public class CountSubarraysWhereMaxElementAppearsAtLeastKTimes {
    public static void main(String[] args) {
    //测试代码
    CountSubarraysWhereMaxElementAppearsAtLeastKTimes fun = new CountSubarraysWhereMaxElementAppearsAtLeastKTimes();
    Solution solution= fun.new Solution();
    solution.countSubarrays(new int[]{1,3,2,3,3},2);
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public long countSubarrays1(int[] nums, int k) {
        int len = nums.length;
        Map<Integer,Integer> count =new HashMap<>();
        int max=0;
        long res=0;
        for (int i = 0; i < len; i++) {
            max=Math.max(max,nums[i]);
            count.put(nums[i],count.getOrDefault(nums[i],0)+1);
        }
        if(count.get(max)<k) return 0;
        int counz=0;
        int l=0;
        for (int i = 0; i < len; i++) {
            if(nums[i]==max){
                counz++;
            }
            while (counz>=k){
                res+=(len-i);
                if(nums[l]==max) counz--;
                l++;
            }
        }
        return res;
    }

    public long countSubarrays2(int[] nums, int k) {
        int n = nums.length;
        int mx = Arrays.stream(nums).max().getAsInt();
        List<Integer> pos = new ArrayList<>();
        pos.add(-1);
        //只统计最大值的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] == mx) {
                pos.add(i);
            }
        }
        //至少保证窗口内有k个元素
        //r=l+k-1
        int left = 1, right = k;
        long ans = 0;
        //然后相乘组合
        while (right < pos.size()) {
            ans += (long)(pos.get(left) - pos.get(left - 1)) * (n - pos.get(right));
            left++;
            right++;
        }
        return ans;
    }
    public long countSubarrays(int[] nums, int k) {
        int mx = Arrays.stream(nums).max().getAsInt();
        long ans = 0;
        int cnt = 0, left = 0;
        for (int x : nums) {
            if (x == mx) {
                cnt++;
            }
            while (cnt == k) {
                if (nums[left] == mx) {
                    cnt--;
                }
                left++;
            }
            ans += left;
        }
        return ans;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
